﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace MergulhoGrafo
{
    class ConjuntoA
    {
        List<Vertice> todosVertices = new List<Vertice>();
        List<Aresta> todasAresta = new List<Aresta>();

        public ConjuntoA()
        {
            TextReader txtEntradaProblema = new StreamReader("../../entrada.txt");
            int numeroVertices = Convert.ToInt32(txtEntradaProblema.ReadLine());

            for (int i = 0; i < numeroVertices; i++)
            {
                Vertice noTemp = new Vertice(i);
                this.todosVertices.Add(noTemp);

                string read = txtEntradaProblema.ReadLine();

                string[] linha = read.Split(' ');

                for (int j = 0; j < linha.Length; j++)
                {
                    int numeroRef = Convert.ToInt32(linha[j]);
                    this.InserirAresta(numeroRef, noTemp);
                }
            }

            int numTwirl = Convert.ToInt32(txtEntradaProblema.ReadLine());

            for (int i = 0; i < numTwirl; i++)
            {
                int index_vert = Convert.ToInt32(txtEntradaProblema.ReadLine());

                Aresta temp = todasAresta.Find(v => v.IndexAresta == index_vert);
                temp.EhTorcida = true;
            }

            List<Aresta> arvoreGeradora = GerarArvoreGeradora(todosVertices[0]);
            List<Aresta> Acontraido = this.ContrairA(todasAresta, arvoreGeradora);
            Console.ReadKey();
        }

        private void InserirAresta(int numeroRef, Vertice noTemp)
        {
            Aresta temp = this.todasAresta.Find(a => a.IndexAresta == numeroRef);

            if (temp == null)
            {
                temp = new Aresta(numeroRef);
                temp.A = noTemp;
                this.todasAresta.Add(temp);                
            }
            else
            {
                temp.B = noTemp;
            }
            
            if (noTemp.ListaArestas == null)
            {
                noTemp.ListaArestas = new List<Aresta>();
            }
            noTemp.ListaArestas.Add(temp);
        }

        public List<Aresta> GerarArvoreGeradora(Vertice raiz)
        {
            List<Aresta> arestasDaArvoreGeradora = new List<Aresta>();
            List<Vertice> verticesParaVisitar = new List<Vertice>();
            List<Vertice> verticesVisitados = new List<Vertice>();
            verticesParaVisitar.Add(raiz);

            while (verticesParaVisitar.Count > 0)
            {
                Vertice no = verticesParaVisitar[0];
                verticesParaVisitar.RemoveAt(0);
                verticesVisitados.Add(no);

                foreach (Aresta aresta in no.ListaArestas)
                {
                    Vertice oposto = aresta.verticeOposto(no);

                    if (arestasDaArvoreGeradora.Find(a => a.A.Id == oposto.Id || a.B.Id == oposto.Id) == null)
                    {
                        arestasDaArvoreGeradora.Add(aresta);
                        verticesParaVisitar.Add(oposto);
                    }
                }
            }
            return arestasDaArvoreGeradora;
        }

        public List<Aresta> ContrairA(List<Aresta> mapa, List<Aresta> arvoreGeradora)
        {
            foreach (Aresta aresta in arvoreGeradora)
            {
                mapa.RemoveAll(a => a.IndexAresta == aresta.IndexAresta);
            }
            return mapa;
        }
    }
}
